//最长递增子序列的个数
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n,1);
        //len[i]表示以i位置元素为结尾的所有子序列中，最长递增子序列的长度
        auto count = len;
        //count[i]表示以i位置元素为结尾的所有子序列中，最长递增子序列的个数
        int retVal = 0;
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j < i ; ++j)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j]+1 == len[i])
                    {
                        count[i]+=count[j];
                    }
                    else if(len[j]+1 > len[i])
                    {
                        len[i] = len[j]+1;
                        count[i] = count[j];
                    }
                    len[i] = max(len[j]+1,len[i]);
                }
            }
        }
        int maxval = len[0];
        int ret = 1;
        for(size_t i = 1 ; i < n ; ++i)
        {
            if(len[i] == maxval) ret+=count[i];
            else if(len[i] > maxval) maxval = len[i],ret = count[i];
        }
        return ret;
    }
};

//最长数对链
class Solution {
public:
    class Compare
    {
        public:
        bool operator()(vector<int> p1,vector<int> p2)
        {
            return p1[0] < p2[0];
        }
    };
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),Compare());
        int n = pairs.size();
        vector<int> dp(n,1);//dp[i]表示以i位置元素为结尾的所有子数链中的最长数对链长度
        int ret = 1;
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j < i ; ++j)
            {
                if(pairs[j][1] < pairs[i][0])
                {
                    dp[i] = max(dp[j]+1,dp[i]);
                }
            }
            ret = max(dp[i],ret);
        }
        return ret;
    }
};

//最长定差子序列
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int,int> hash;
        //dp[i]表示以i位置元素为结尾的所有子序列中的最长等差子序列的长度
        int ret = 1;
        for(size_t i = 0 ; i < n ; ++i)
        {
            int temp = arr[i] - difference;
            if(hash.find(temp) == hash.end())
            {
                hash[arr[i]] = 1;
            }
            else 
            {
                hash[arr[i]] = hash[temp]+1;
            }
            ret = max(hash[arr[i]],ret);
        }
        return ret;
    }
};

//最长的斐波那契子序列的长度
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //优化
        //... a  b  c
        //a = c-b, b = c-a , c = a+b
        //设k为a，i为b，j为c
        //若a存在，且a < b : dp[i][j] = dp[k][i]+1;
        //否则为2
        int n = arr.size();
        unordered_map<int,int> hash;
        for(size_t i = 0 ; i < n ; ++i) hash[arr[i]] = i;

        vector<vector<int>> dp(n,vector<int>(n,2));
        if(n < 3)
        {
            return 0;
        }
        //dp[i][j]表示以i位置元素及其j位置元素为结尾的所有子序列中的最长斐波那契子序列的长度
        int ret = 0;
        for(size_t j = 2 ; j < n ; ++j)
        {
            for(size_t i = 1 ; i < j ; ++i)
            {
                int a = arr[j] - arr[i];
                if(hash.count(a))
                {
                    int k = hash[a];
                    if(k < i)
                    {
                        dp[i][j] = dp[k][i]+1;
                        ret = max(dp[i][j],ret);
                    }
                }
            }
        }
        return ret < 3 ? 0 : ret;
    }
};

//最长等差数列
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        //等差子序列的定义：nums[k],nums[i],nums[j] => nums[i]-nums[k] = nums[j]-nums[i]
        //必须固定两个数
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>(n,2));
        //dp[i][j]表示以i位置及其j位置元素为结尾的最长等差子序列的长度
        unordered_map<int,int> hash;
        hash[nums[0]] = 0;
        int ret = 2;
        //先固定nums[i]
        for(size_t i = 1 ; i < n ; ++i)
        {
            //再固定nums[j]
            for(size_t j = i + 1 ; j < n ; ++j)
            {
                int a = 2*nums[i]-nums[j];
                if(hash.count(a))
                    dp[i][j] = dp[hash[a]][i]+1;
                ret = max(dp[i][j],ret);
            }
            //一边dp，一边更新下标和元素之间的绑定关系
            hash[nums[i]] = i;
        }
        return ret;
    }
};

//等差数列划分II--子序列
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long long,vector<int>> hash;
        //把元素值与下标数组进行绑定，放入hash中
        for(size_t i = 0 ; i < n ; ++i) hash[nums[i]].push_back(i);

        //必须固定两个数，才能确定一个等差数列，用二维dp
        vector<vector<long long>> dp(n,vector<long long>(n));
        //k i j
        //先固定倒数第一个数
        int ret = 0;
        for(size_t j = 2 ; j < n ; ++j)
        {
            for(size_t i = 1 ; i < j ; ++i)
            {
                long long a = 2*static_cast<long long>(nums[i])-nums[j];
                if(hash.count(a))
                {
                    for(auto& k : hash[a])
                    {
                        if(k < i)
                        {
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }
                }
                ret += dp[i][j];
            }
        }
        return ret;
    }
};


